package matrix;

/**
 * 240. 搜索二维矩阵 II
 * 编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。
 * 该矩阵具有以下特性：
 * 每行的元素从左到右升序排列。
 * 每列的元素从上到下升序排列。
 * <p>
 * 示例 1：
 * 输入：matrix = [
 * [1,4,7,11,15],
 * [2,5,8,12,19],
 * [3,6,9,16,22],
 * [10,13,14,17,24],
 * [18,21,23,26,30]
 * ],
 * target = 5
 * 输出：true
 * <p>
 * 示例 2：
 * 输入：matrix = [
 * [1,4,7,11,15],
 * [2,5,8,12,19],
 * [3,6,9,16,22],
 * [10,13,14,17,24],
 * [18,21,23,26,30]
 * ],
 * target = 20
 * 输出：false
 */
public class Problem_240 {
    public static void main(String[] args) {
        System.out.println(new Problem_240().searchMatrix_2(new int[][]{
                {1, 4, 7, 11, 15},
                {2, 5, 8, 12, 19},
                {3, 6, 9, 16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
        }, 10));
    }

    /**
     * 方法二：二分查找
     * 由于矩阵 matrix 中每一行的元素都是升序排列的，
     * 因此我们可以对每一行都使用一次二分查找，判断 target 是否在该行中，从而判断 target 是否出现过。
     */
    public boolean searchMatrix_1(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            int[] nums = matrix[i];

            // 由于 每列的元素从上到下升序排列，所以如果target小于当前行的第一个元素，则一定也小于后面所有行的第一个元素，
            // 而每行的第一个元素又是整行中最小的元素，此时整个矩阵中一定没有结果。
            if (target < nums[0]) {
                return false;
            }
            // 本行找不到，直接跳过进行下一行
            if (target > nums[nums.length - 1]) {
                continue;
            }

            // 开始进行单层的二分查找
            int left = 0;
            int right = nums.length - 1;
            while (left <= right) {
                int mid = left + (right - left) / 2;
                if (nums[mid] == target) {
                    return true;
                } else if (nums[mid] > target) {
                    right = mid - 1;
                } else {
                    left = mid + 1;
                }
            }
        }

        return false;
    }

    /**
     * 方法二：Z 字形查找
     * 我们可以从矩阵 matrix 的右上角 (0,n−1) 位置进行搜索。
     * 在每一步的搜索过程中，如果我们位于位置 (x,y)，那么我们希望在以 matrix 的左下角为左下角、以 (x,y) 为右上角的矩阵中进行搜索，
     * 即行的范围为 [x,m−1]，列的范围为 [0,y]：
     * 如果 matrix[x,y]=target，说明搜索完成；
     * 如果 matrix[x,y]>target，由于每一列的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 y 列的元素都是严格大于 target 的，因此我们可以将它们全部忽略，即将 y 减少 1；
     * 如果 matrix[x,y]<target，由于每一行的元素都是升序排列的，那么在当前的搜索矩阵中，所有位于第 x 行的元素都是严格小于 target 的，因此我们可以将它们全部忽略，即将 x 增加 1。
     * 在搜索的过程中，如果我们超出了矩阵的边界，那么说明矩阵中不存在 target。
     */
    public boolean searchMatrix_2(int[][] matrix, int target) {
        int m = matrix.length;
        int n = matrix[0].length;

        int x = 0, y = n - 1;
        while (y >= 0 & x < m) {
            if (matrix[x][y] == target) {
                return true;
            } else if (matrix[x][y] > target) {
                y--;
            } else {
                x++;
            }
        }

        return false;
    }

}
